package ca.krakenpower.kvoxels;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/*
 * -each node has an associated (pre-filtered) voxel brick approximating its volume
 */

public class KVoxelOctree {
	
	public final int nodePoolIncrement = 128;
	public final int brickPoolIncrement = 32;
	public final int brickSize;
	public final int borderSize = 0;
	public final int totalBSize;
	public final int brick3Size;
	public final int tBrick3Size;
	
	private int nodePointer;
	private int brickPointer;
	
	private int[] pointerPool, dataPool;
	
	private int[] brickPool;
	
	private int size;
	
	private int maxSubdivisions;
	
	private int nodeExpansions = 0;
	private int brickExpansions = 0;
	private int brickChunks = 0;
	private int nodeChunks = 0;
	
	private int numNodes = 0;
	private int numBricks = 0;
	
	private int maxNodes = 0;
	private int maxBricks = 0;
	
	private Queue<Integer> freeNodeTiles;
	private Queue<Integer> freeBricks;
	
	public KVoxelOctree(int size, int bsize) {
		this.freeNodeTiles = new LinkedList<>();
		this.freeBricks = new LinkedList<>();
		
		this.size = size;
		this.brickSize = bsize;
		totalBSize = brickSize + borderSize + borderSize;
		brick3Size = brickSize * brickSize * brickSize;
		tBrick3Size = totalBSize * totalBSize * totalBSize;
		
		this.brickPointer = 0;
		this.brickPool = new int[brickPoolIncrement * tBrick3Size];
		
		this.nodePointer = 0;
		this.pointerPool = new int[nodePoolIncrement];
		this.dataPool = new int[nodePoolIncrement];
		
		putNode(packPointer(0, false, false),
				KVoxels.packRGBA(0, 0, 0, 0));
		
		computeMaxSubdivisions();
		
	}
	
	private void computeMaxSubdivisions() {
		float fsize = size;
		maxSubdivisions = 0;
		int brickSubs = 0;
		float fbrickSize = brickSize;
		
		while (fbrickSize > 2) {
			fbrickSize /= 2;
			brickSubs++;
		}
		
		while (fsize > 1) {
			fsize /= 2;
			maxSubdivisions++;
		}
		
		maxSubdivisions -= brickSubs;
	}
	
	public int getMaxSubdivisions() {
		return maxSubdivisions;
	}
	
	public int getNumNodes() {
		return numNodes;
	}
	
	public int getNumBricks() {
		return numBricks;
	}
	
	public int getMaxNodes() {
		return maxNodes;
	}
	
	public int getMaxBricks() {
		return maxBricks;
	}
	
	public int getNumVoxels() {
		return numBricks * (totalBSize * totalBSize * totalBSize);
	}
	
	public int getNumBrickChunks() {
		return brickChunks;
	}
	
	public int getNumNodeChunks() {
		return nodeChunks;
	}
	
	public void chunkSubnodes(int nodeIndex) {
		int node = pointerPool[nodeIndex];
		
		if (isMaxSubdivision(node) ||
				getChildPointer(node) == 0) {
			return;
		}
		
		int cIndex = getChildPointer(node);
		for (int c = cIndex; c < cIndex + 8; c++) {
			chunkSubnodes(c);
			if (!isMaxSubdivision(pointerPool[c]) ||
					isBrick(pointerPool[c])) {
				return;
			}
		}
		
		int cmp = dataPool[cIndex];
		
		for (int c = cIndex; c < cIndex + 8; c++) {
			if (dataPool[c] != cmp) {
				return;
			}
		}
		
		freeNodeTile(cIndex);
		node = packPointer(0, true, false);
		pointerPool[nodeIndex] = node;
		dataPool[nodeIndex] = cmp;
		nodeChunks++;
		numNodes -= 8;
	}
	
	private int nextNodeTilePointer() {
		if (!freeNodeTiles.isEmpty()) {
			return freeNodeTiles.peek();
		}
		return nodePointer;
	}
	
	private int nextBrickPointer() {
		if (!freeBricks.isEmpty()) {
			return freeBricks.peek();
		}
		return brickPointer;
	}
	
	public int packBrickIndex(int x, int y, int z) {
		if (x < 0) x = 0;
		if (y < 0) y = 0;
		if (z < 0) z = 0;
		if (x >= brickSize) x = brickSize - 1;
		if (y >= brickSize) y = brickSize - 1;
		if (z >= brickSize) z = brickSize - 1;
		int bi = x + borderSize;
		bi += (y + borderSize) * totalBSize;
		bi += (z + borderSize) * totalBSize * totalBSize;
		
		return bi;
	}
	
	public Vector3 unpackBrickIndex(int bi) {
		int x, y, z;
		x = (bi % totalBSize) - borderSize;
		y = ((bi % (totalBSize * totalBSize)) - x) - borderSize;
		z = (bi - y - x) - borderSize;
		
		return Vector3.get(x, y, z);
	}
	
	public int getSize() {
		return size;
	}
	
	public void shrinkPools() {
		int[] temp = pointerPool;
		pointerPool = Arrays.copyOf(temp, nodePointer);
		temp = dataPool;
		dataPool = Arrays.copyOf(temp, nodePointer);
		temp = brickPool;
		brickPool = Arrays.copyOf(temp, brickPointer);
	}
	
	public int[] getNodePool() {
		return pointerPool;
	}
	
	public int[] getDataPool() {
		return dataPool;
	}
	
	public int[] getBrickPool() {
		return brickPool;
	}
	
	public int get(float x, float y, float z, float vSize) {
		
		int currentNode = 0;
		float cx, cy, cz, nodeSize;
		cx = x / size;
		cy = y / size;
		cz = z / size;
		nodeSize = size;
		
		boolean done = false;
		while (!done && vSize > nodeSize) {
			int currentPointer = pointerPool[currentNode];
			if (isMaxSubdivision(currentPointer)) {
				done = true;
			} else {
				int child = getChildPointer(currentPointer);
				int offx, offy, offz;
				offx = (int) (2 * cx);
				offy = (int) (2 * cy);
				offz = (int) (2 * cz);
				
				currentNode = child + (offx + 2 * offy + 4 * offz);
				
				cx = 2 * cx - offx;
				cy = 2 * cy - offy;
				cz = 2 * cz - offz;
				
				nodeSize /= 2;
			}
		}
		
		if (isBrick(pointerPool[currentNode])) {
			int offx, offy, offz;
			offx = (int) (brickSize * cx);
			offy = (int) (brickSize * cy);
			offz = (int) (brickSize * cz);
			
			int brick = dataPool[currentNode];
			int bi = packBrickIndex(offx, offy, offz);
			
			return brickPool[brick + bi];
		}
		
		return dataPool[currentNode];
		
	}
	
	public void insert(int voxel, float x, float y, float z) {

		int currentNode = 0;
		int depth = 0;
		float cx, cy, cz;
		cx = x / size;
		cy = y / size;
		cz = z / size;
		
		boolean done = false;
		while (!done) {
			depth++;
			int currentPointer = pointerPool[currentNode];
			if (isMaxSubdivision(currentPointer) || depth >= maxSubdivisions) {
				done = true;
			} else {
				int child = getChildPointer(currentPointer);
				if (child == 0) {
					child = nextNodeTilePointer();
					boolean terminal = (depth >= maxSubdivisions - 1);
					currentPointer = packPointer(child, false, isBrick(currentPointer));
					int[] pointers, data;
					pointers = new int[8];
					data = new int[8];
					Arrays.fill(pointers, packPointer(0, terminal, false));
					Arrays.fill(data, dataPool[currentNode]);
					
					putNodeTile(pointers, data);
					
					pointerPool[currentNode] = currentPointer;
				}
				
				int offx, offy, offz;
				offx = (int) (2 * cx);
				offy = (int) (2 * cy);
				offz = (int) (2 * cz);
				
				currentNode = child + (offx + 2 * offy + 4 * offz);
				
				cx = 2 * cx - offx;
				cy = 2 * cy - offy;
				cz = 2 * cz - offz;
			}
			
		}
		
		int brickIndex;
		if (!isBrick(pointerPool[currentNode])) {
			pointerPool[currentNode] |= (1 << 30);
			int clr = dataPool[currentNode];
			
			int[] brick = new int[totalBSize * totalBSize * totalBSize];
			Arrays.fill(brick, clr);
			
			brickIndex = putBrick(brick);
			dataPool[currentNode] = brickIndex;
		} else {
			brickIndex = dataPool[currentNode];
		}
		
		int offx, offy, offz;
		offx = (int) (brickSize * cx);
		offy = (int) (brickSize * cy);
		offz = (int) (brickSize * cz);
		
		int bi = packBrickIndex(offx, offy, offz);
		brickPool[brickIndex + bi] = voxel;
		
		if (isChunkableBrick(brickIndex)) {
			freeBrick(dataPool[currentNode]);
			pointerPool[currentNode] = packPointer(getChildPointer(pointerPool[currentNode]), isMaxSubdivision(pointerPool[currentNode]), false);
//			double a = (voxel & 0xFF) / 255.0;
//			a = 1 - Math.pow(1 - a, brickSize);
//			voxel = ((int)(a * 255) & 0xFF) | (voxel & 0xFFFFFF00);
			dataPool[currentNode] = voxel;
			brickChunks++;
			numBricks--;
		}
		
	}
	
	public int getNodeExpansions() {
		return nodeExpansions;
	}
	
	public int getBrickExpansions() {
		return brickExpansions;
	}
	
	private void expandNodePools() {
		int[] temp = pointerPool;
		pointerPool = Arrays.copyOf(temp, temp.length + nodePoolIncrement);
		temp = dataPool;
		dataPool = Arrays.copyOf(temp, temp.length + nodePoolIncrement);
		nodeExpansions++;
	}
	
	private void expandBrickPool() {
		brickExpansions++;
		int[] temp = brickPool;
		brickPool = Arrays.copyOf(temp, temp.length + brickPoolIncrement * tBrick3Size);
	}
	
	private void putNode(int pointer, int data) {
		while (nodePointer >= pointerPool.length) {
			expandNodePools();
		}
		
		pointerPool[nodePointer] = pointer;
		dataPool[nodePointer] = data;
		nodePointer++;
		numNodes++;
		
		if (numNodes > maxNodes) {
			maxNodes = numNodes;
		}
	}
	
	private void freeNodeTile(int index) {
		freeNodeTiles.offer(index);
		if (index == nodePointer - 1) {
			nodePointer--;
		}
	}
	
	private void putNodeTile(int[] pointer, int[] data) {
		int temp = -1;
		if (!freeNodeTiles.isEmpty()) {
			int nodeTile = freeNodeTiles.remove();
			temp = nodePointer;
			nodePointer = nodeTile;
		}
		
		for (int i = 0; i < 8; i++) {
			putNode(pointer[i], data[i]);
		}
		
		if (temp >= 0) {
			nodePointer = temp;
		}
	}
	
	private void freeBrick(int index) {
		freeBricks.offer(index);
		if (index == brickPointer - 1) {
			brickPointer--;
		}
	}
	
	private int putBrick(int[] brick) {
		int temp = -1;
		
		if (!freeBricks.isEmpty()) {
			int brickIndex = freeBricks.remove();
			temp = brickPointer;
			brickPointer = brickIndex;
		}
		
		while (brickPointer + tBrick3Size >= brickPool.length) {
			expandBrickPool();
		}
		
		int index = brickPointer;
		
		for (int i = brickPointer; i < brickPointer + tBrick3Size; i++) {
			brickPool[i] = brick[i - brickPointer];
		}
		
		brickPointer += tBrick3Size;
		
		numBricks++;
		
		if (numBricks > maxBricks) {
			maxBricks = numBricks;
		}
		
		if (temp >= 0) {
			brickPointer = temp;
		}
		
		return index;
	}
	
	private static int getChildPointer(int pointer) {
		return pointer & 0x3FFF_FFFF;
	}
	
	private static boolean isMaxSubdivision(int pointer) {
		return (((pointer >> 31) & 0x1) == 1);
	}
	
	private static boolean isBrick(int pointer) {
		return (((pointer >> 30) & 0x1) == 1);
	}
	
	private static int packPointer(int address, boolean maxSubdivision, boolean isBrick) {
		int pointer = (address & 0x3FFF_FFFF);
		pointer |= (maxSubdivision) ? (1 << 31) : 0;
		pointer |= (isBrick) ? (1 << 30) : 0;
		
		return pointer;
	}
	
	private boolean isChunkableBrick(int brickIndex) {
		int cmp = brickPool[brickIndex + packBrickIndex(0, 0, 0)];
		boolean visible = ((cmp & 0xFF) > 0);
		
		for (int i = 0; i < brickSize; i++) {
			for (int j = 0; j < brickSize; j++) {
				for (int k = 0; k < brickSize; k++) {
//					if (!visible) {
//						if ((brickPool[brickIndex + packBrickIndex(i, j, k)] & 0xFF) != 0) {
//							return false;
//						}
//					} else {
						if (brickPool[brickIndex + packBrickIndex(i, j, k)] != cmp) {
							return false;
						}
//					}
				}
			}
		}
		
		return true;
	}
	

}
